// https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/
// Created by ade on 2022/7/21.
//
#include <iostream>
#include <vector>
#include <map>


using namespace std;

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};

/*
 *                            1
 *                   2                3
 *              4        5        6        7
 *           8     9  10   11  13  14  15     16
 *
 * */

class Solution {
public:
    map<int, Node*> myMap;
    Node* connect(Node* root) {
        if (!root) return root;
        dfs(root, 0);
        return root;
    }

    void dfs(Node* node, int index) {
        if (node) {
            if (myMap[index] != nullptr) {
                myMap[index]->next = node;
            }
            myMap[index] = node;
            dfs(node->left, index + 1);
            dfs(node->right, index + 1);
        }
    }

    Node* init() {
        // [1,2,2,3,3,null,null,4,4]
        Node* head1 = new Node(1);
        Node* head2 = new Node(-9);
        Node* head3 = new Node(8);
        Node* head4 = new Node(4);
        Node* head5 = new Node(-3);
        Node* head6 = new Node(-3);
        Node* head7 = new Node(-6);
        Node* head8 = new Node(-6);
        Node* head9 = new Node(-4);
        Node* head10 = new Node(-9);
        Node* head11 = new Node(6);
        head1->right = head2;
        head2->right = head3;
 
        head3->left = head4;
        head3->right = head5;
        head5->left = head6;
        head6->left = head7;
        head7->right = head8;
        head8->left = head9;
        head8->right = head10;
        head10->left = head11;
        return head1;
    }
};

int main() {
    Solution so;
    Node* head = so.init();
    so.connect(head);
    return 0;
}